class Solution:
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        f = [10000] * (n+1)
        f[0] = 0
        f[1] = 1
        for i in range(2,n+1):
            j=1
            while j*j<=i:
                f[i] = min(f[i],f[i-j*j]+1)
                j+=1
        return f[-1]
s = Solution()
m = s.numSquares(12)
print(m)